﻿#include<queue>
//#include <algorithm>  
#include <functional>  
#include"XHuffmanTree.h"
//优先队列大于的回调函数
static struct Less {
	bool operator()(LPXHfmNode& _Left, LPXHfmNode& _Right) const
	 {
		return _Left->data().count > _Right->data().count;
	}
};

//根据字典创建树
void XHuffmanTree::creationTree()
{
	std::priority_queue<LPXHfmNode, std::vector<LPXHfmNode>, Less> queue;
	//原始字典生成单独的节点插入优先队列
	for (auto& data : m_dictionaries)
	{
		LPXHfmNode node = new XHfmNode({ data.first, data.second.count, data.second.code });
		queue.push(node);
	}
	//生成哈夫曼树
	XHfmNode* LPparent = NULL;//父节点
	XHfmNode* LPleft = NULL;//左节点
	XHfmNode* LPright = NULL;//右节点
	while (!queue.empty())
	{
		XHfmNode* LPNode = queue.top();
		queue.pop();
		if (LPleft == NULL)
		{
			LPleft = LPNode;
		}
		else
		{
			LPright = LPNode;
			//创建空父节点，并建立关系
			LPparent = new XHfmNode({ 0, LPleft->data().count + LPright->data().count, NULL });
			LPparent->setLeftChild(LPleft);
			LPparent->setRightChild(LPright);
			queue.push(LPparent);
			LPleft = NULL;
			LPright = NULL;
		}

	}
	root = LPparent;
}
